ABC174 (2020.8.2) 全场题解

今天突然想到把所有 AK 的比赛都写一个全场题解,就从这场开始吧。

注:本文中给出的代码均为赛时 AC 代码。

A - Air Conditioner Link

简单来说就是判断温度是否大于 3030 度。

代码:

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;

int n; 

int main() {
	scanf("%d", &n);
	if(n >= 30) {
		puts("Yes");
	}
	else {
		puts("No");
	}
	return 0;
}

B - Distance Link

判断二维平面内 nn 个点中,有多少个点到原点的距离不小于 dd。我们代入距离公式,读入每个点都算一遍即可。我们这里设置的浮点数运算允许误差范围为 10610^{-6}

代码:

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, d, tot;
double dis(ll x, ll y) {
	return sqrt(1.0*x*x+1.0*y*y);
}

int main() {
	scanf("%lld%lld", &n, &d);
	for(ll i=1;i<=n;i++) {
		ll x, y;
		scanf("%lld%lld", &x, &y);
		if(dis(x, y) - d <= 1e-6) {
			++tot;
		}
	}
	printf("%lld\n", tot);
	return 0;
}

C - Repsept Link

求每个数位全部为 77 的,是 kk 的倍数的第一个数的位数(即包含多少个 77)。

一道简单数学题,我们有如下推导:

设 ai=777共 i 个ai+1=ai×10+7{a+b(amodk)+(bmodk)(modk)a×b(amodk)×(bmodk)(modk)ai+1(aimodk)×10+7(modk)\begin{aligned} \text{设}\ a_i=&\underbrace{77\cdots 7}_{\text{共}\ i\ \text{个}}\\ a_{i+1}=&a_i\times 10+7\\ \because& \begin{cases} a+b\equiv (a\mod k)+(b\mod k)&\pmod k\\ a\times b\equiv (a\mod k)\times (b\mod k)&\pmod k \end{cases} \\ \therefore& a_{i+1}\equiv (a_i\mod k)\times 10+7\pmod k \end{aligned}

发现余数有递推关系,我们只需要循环维护这个余数,到为 00 或循环时退出循环即可。

代码:

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;

bool _;
int k, md, i = 1;
int book[N];

int main() {
	scanf("%d", &k);
	md = 7 % k;
//	printf("%d\n", md);
	while(!book[md]) {
		if(!md) {
			_ = true;
			break;
		}
		book[md] = 1;
		md = (md * 10 + 7) % k;
//		printf("%d\n", md);
		++i;
	}
	if(!_) {
		puts("-1");
	}
	else {
		printf("%d\n", i);
	}
	return 0;
}

D - Alter Altar Link

赛后找到这题的一个类似的题,忘了题号了,大概说男生女生排座位,通过交换使得所有女生在男生前面。

有一串由 RW 组成的序列,每次可以选择任意两个位置交换,或者更改一个位置的字母。要使用最少的步数使得 R 全部在 W 前方。

我们统计最后一个 W 以及 R 的总个数,进行一些数学推导即可。

代码:

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;

int n, tot, W, tot2;
string s;

int main() {
	scanf("%d", &n);
	cin>>s;
	for(int i=0;i<n;i++) {
		if(s[i] == 'W') {
			if(!W) {
				W = i;
			}
		}
		else {
			++tot;
		}
	}
	for(int i=0;i<tot;i++) {
		if(s[i] != 'R') {
			++tot2;
		}
	}
	printf("%d\n", min(tot2, n-W));
	return 0;
}

E - Logs Link

nn 个不同长度的木头,进行 kk 次切分,分成两个长度之和为切分前长度的木头。输出切分完成后长度最长的木头的最小长度(向上取整)。

我们考虑二分答案——在 11 和最长的长度间二分,每次求出使最长木头的长度最小不超过 midmid 时,需要的切分次数,当满足题意时记录 ansans

代码:

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;

int n, k, l = 1, r, ans;
int a[N];

bool f(int x) {
	int t = 0;
	for(int i=1;i<=n;i++) {
		if(a[i] % x == 0) {
			t += a[i] / x - 1;
		}
		else {
			t += a[i] / x;
		}
	}
	if(t > k) {
		return false;
	}
	else {
		return true;
	}
}

int main() {
	scanf("%d%d", &n, &k);
	for(int i=1;i<=n;i++) {
		scanf("%d", &a[i]);
		r = max(r, a[i]);
		ans = max(ans, a[i]);
	}
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(f(mid)) {
			ans = mid;
			r = mid - 1;
		}
		else {
			l = mid + 1;
		}
	}
	printf("%d\n", ans);
	return 0;
}

F - Range Set Query Link

有一个长度为 nn 的数组,每个位置有一个颜色。qq 次询问,每次求出 alara_l\sim a_r 中共有多少种不同的颜色。

有没有感觉很熟悉?HH 的项链!

代码:

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+5;

int a[N], b[N], book[N], ans[N], n, q;

struct Node {
    int l, r, id;
    bool operator < (const Node &a) const {
		return r < a.r;
	}
}p[N];
void add(int n, int u) {
	for(;n<=N;n+=n&(-n)) {
		b[n] += u;
	}
}
int sum(int n) {
	int res = 0;
	for(;n;n-=n&(-n)) {
		res += b[n];
	}
	return res;
}

int main()
{
	scanf("%d%d", &n, &q);
	for(int i=1;i<=n;i++) {
		scanf("%d", &a[i]);
	}
	for(int i=1;i<=q;i++) {
		scanf("%d%d", &p[i].l, &p[i].r);
		p[i].id = i;
	}
	sort(p+1, p+1+q);
//	puts("Sorted. ");
	int nxt = 1;
    for(int i=1;i<=q;i++) {
//   	printf("For: i=%d\n", i);
		for(int j=nxt;j<=p[i].r;j++) {
//			printf("\tj=%d\n", j);
			if(book[a[j]]) {
				add(book[a[j]], -1);
			}
			add(j, 1);
			book[a[j]] = j;
		}
		nxt = p[i].r + 1;
		ans[p[i].id] = sum(p[i].r) - sum(p[i].l-1);
	}
	for(int i=1;i<=q;i++) {
		printf("%d\n", ans[i]);
	}
	return 0;
}

完结撒花!